package com.kjc.demo.basic.algorithmtest;

public class Test1009 {
	//冒泡排序
	public void bubbleSort(int[] arr) {
		for(int i=0 ;i <arr.length-1;i++) {
			for(int j=0 ; j<arr.length-i-1;j++) {
				if(arr[j] > arr[j+1]) {
					int temp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = temp;
				}
			}
		}
	}
	//选择排序
	public void selectSort(int[] arr) {
		for(int i=0 ;i <arr.length -1 ;i++) {
			int min = i;
			for(int j=i+1;j<arr.length;j++) {
				if(arr[min] > arr[j]) {
					min = j;
				}
			}
			if(min != i) {
				int temp = arr[min];
				arr[min] = arr[i];
				arr[i] = temp;
			}
		}
	}
	//插入排序
	public void insertSort(int[] arr) {
		for(int i=1;i<arr.length;i++) {
			
			int j = i;
			while(j > 0 && arr[j] < arr[j-1]) {
				int temp = arr[j];
				arr[j] = arr[j-1];
				arr[j-1] = temp;
				j--;
			}
		}
	}
	//快速排序
	public void quickSort(int[] arr,int start ,int end) {
		int i = start;
		int j = end;
		int pre = arr[0];
		while(i<j) {
			while(i < j && arr[j] > pre) {
				j--;
			}
			while(i < j && arr[i] < pre) {
				i++;
			}
			if(i<j && arr[i] == arr[j]) {
				i++;
			}else {
				int temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}
		}
		if(i-1 > start) {
			quickSort(arr,start,i-1);
		}
		if(j+1 < end) {
			quickSort(arr,j+1,end);
		}
	}
	//归并排序
	//堆排序
	//希尔排序
	public void shellSort(int[] arr) {
		for(int gap = arr.length/2; gap>0;gap=gap/2) {
			for(int i= gap;i<arr.length;i++) {
				int j=i;
				while(j-gap > 0&& arr[j] < arr[j-gap]) {
					int temp = arr[j];
					arr[j] = arr[j-gap];
					arr[j-gap] = temp;
					j=j-gap;
				}
			}
		}
	}
	//基数排序
}
